package dynamic;

/**题目：抢劫连排房子
 * y: a[]{8,1,2,9,6}
 * 要求计算最大值，唯一的限制条件就是数组间计算的数字不能相邻
 * 本地计算结果为：8+9=17
 * @Author Gavin
 * @date 2022.01.09 10:36
 */
public class solution_4 {
    /**
     * 解题思路：本题是一个动态规划题目
     * [8,1,2,9,6]
     * 本题目的状态和状态转移的方程为：
     *                                      house       money
     *  一个房子和能抢劫的最大money为：      8           8
     *  二个房子和能抢劫的最大money为：     8,1          8
     *  三个房子和能抢劫的最大money为：     8,1,2        max(8,8+2)=10
     *  四个房子和能抢劫的最大money为：     8,1,2,9      max(10,8+9)=17
     *  ...
     *
     *  可以得出规律：
     *  {
     *      d(i)=max(d(i-1),d(i-2)+nums[i])
     *      d(0)=num(10)
     *      d(1)=max(num[0],nums[1])
     *
     *  }
     *
     */
    //Time:O(n) Space:O(n)
    public static int solution(int[] nums){
        if(nums==null||nums.length==0)return 0;
        if(nums.length==1)return nums[0];
        //定义一个状态数组
        int[] d=new int[nums.length];
        d[0]=nums[0];
        d[1]=Math.max(nums[0],nums[1]);
        //i从2开始
        for (int i = 2; i < nums.length; i++) {
            d[i]=Math.max(d[i-1],d[i-2]+nums[i]);
        }
        return d[nums.length-1];
    }

    /**
     * 该方法是上面的优化版本，主要是优化空间复杂度，
     * 因为我们只需要关注前1个和前两个的值就行，所以只需要两个
     * 变量来存储就行了。
     */
    //Time:O(n) Space:O(1)
    public int solution_2(int[] nums){
        if(nums==null||nums.length==0)return 0;
       int prev1=0,prev2=0;
       for (int num:nums){
           int cur=Math.max(prev1,prev2+num);
           prev2=prev1;
           prev1=cur;
       }
       return prev1;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{8,1,2,8,9};
        System.out.println(solution(arr));
    }
}
